use ethnum::i256;
use rand::Rng;

fn rand_int(l: i128, r: i128) -> i128 {
    let mut rng = rand::thread_rng();
    rng.gen_range(l..r)
}

fn gcd(a: i128, b: i128) -> i128 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn quick_power(a: i128, b: i128, p: i128) -> i128 {
    let mut res = 1;
    let mut a = i256::from(a);
    let mut b = b;
    let p = i256::from(p);
    while b > 0 {
        if b & 1 != 0 {
            res = (i256::from(res) * a % p).as_i128();
        }
        a = a * a % p;
        b >>= 1;
    }
    res
}

fn miller_rabin(n: i128) -> bool {
    if n < 3 || n % 2 == 0 {
        return n == 2;
    }
    let mut a = n - 1;
    let mut b = 0;
    while a % 2 == 0 {
        a /= 2;
        b += 1;
    }
    for _ in 0..10 {
        let x = rand_int(2, n - 1);
        let mut v = quick_power(x, a, n);
        if v == 1 {
            continue;
        }
        let mut j = 0;
        while j < b {
            if v == n - 1 {
                break;
            }
            v = (i256::from(v) * i256::from(v) % i256::from(n)).as_u128() as i128;
            j += 1;
        }
        if j == b {
            return false;
        }
    }
    true
}

fn pollard_rho(n: i128) -> i128 {
    let mut s = 0;
    let mut t = 0;
    let c = rand_int(1, n - 1);
    let mut step = 0;
    let mut goal = 1;
    let mut value = 1;
    let f = |x: i128| -> i128 {
        (i256::from(x) * i256::from(x) + i256::from(c) % i256::from(n)).as_i128()
    };
    loop {
        for _ in 0..goal {
            t = f(t);
            value = (i256::from(value) * (i256::from(t) - i256::from(s)).abs() % i256::from(n)).as_i128();
            if step % 127 == 0 {
                let d = gcd(value, n);
                if d > 1 {
                    return d;
                }
            }
            step += 1;
        }
        let d = gcd(value, n);
        if d > 1 {
            return d;
        }
        goal *= 2;
        s = t;
        value = 1;
    }
}

fn fac(mut n: i128, ans: &mut i128) {
    if n <= *ans || n < 2 {
        return;
    }
    if miller_rabin(n) {
        *ans = (*ans).max(n);
        return;
    }
    let mut p = n;
    while p == n {
        p = pollard_rho(n);
    }
    while n % p == 0 {
        n /= p;
    }
    fac(n, ans);
    fac(p, ans);
}

pub fn find_max_prime_factor(n: u128) -> u128 {
    let mut ans: i128 = 0;
    fac(n as i128, &mut ans);
    ans as u128
}